/**
 *    Copyright (C) 2008  Victor Smirnov <aist11@gmail.com>
 *
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License along
 *    with this program; if not, write to the Free Software Foundation, Inc.,
 *    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 *    See LICENSE.exceptions in the root folder of this project for possible
 *    exceptions
 *
 */

#ifndef _CUBEFS_CORE_MAP_KV_FIND_HPP
#define	_CUBEFS_CORE_MAP_KV_FIND_HPP

#include <cubefs/core/btree/btree.hpp>

namespace cubefs    {
namespace core      {
namespace map       {
namespace kv       {

class Find{};

}
}
}
}

namespace cubefs    {
namespace core      {
namespace btree     {

template <typename Base>
struct Strategy<cubefs::core::map::kv::Find, Base>: public Base {

    typedef Base base;

    typedef typename base::PageMgr                      PageMgr;

    typedef typename base::Page                       Page;
    typedef typename base::Page::ID                   ID;
    typedef typename base::Transaction                        Transaction;

    typedef typename base::PageTypes                  PageTypes;

    typedef typename base::Key                          Key;
    typedef typename base::Value                        Value;


    typedef typename base::NodeBase                    NodeBase;
    typedef typename base::Counters                   Counters;

    typedef typename base::Iterator                   Iterator;

    typedef typename base::NodeDispatcher               NodeDispatcher;
    typedef typename base::RootDispatcher               RootDispatcher;
    typedef typename base::LeafDispatcher               LeafDispatcher;
    typedef typename base::InternalNodeDispatcher         InternalNodeDispatcher;

    typedef typename base::Node2RootMap                 Node2RootMap;
    typedef typename base::Root2NodeMap                 Root2NodeMap;

    static const long Indexes = base::Indexes;


    struct find_le_fn {
        Iterator i_;
        bool rtn;
        NodeBase *node_;

        find_le_fn(PageMgr *mgr0, Transaction *txn0) : i_(mgr0, txn0) {}

        template <typename Node, typename Keys, typename C, typename ForInsert, typename Mgr, typename Txn>
        void operator()(Node *node, Keys key, C c, ForInsert for_insert, Mgr *mgr, Txn *txn) {
            rtn = false;
            Int idx = node->map().FindLE(c, key);
            if (idx >=0)
            {
                if (!node->is_leaf()) {
                    node_ = base::get_child(node, idx, mgr, *txn);
                }
                else {
                    i_ = Iterator(node, idx, mgr, txn);
                    rtn = true;
                }
            }
            else if (for_insert && key > node->map().max_key(c))
            {
                if (!node->is_leaf())
                {
                    idx = node->map().size() - 1;
                    node_ = base::get_child(node, idx, mgr, *txn);
                }
                else
                {
                    Iterator i(node, node->map().size(), mgr, txn);
                    i.setEof(true);
                    i_ = i;
                    rtn = true;
                }
            }
            else {
                i_ = Iterator(mgr, txn);
                rtn = true;
            }
        }
    };

    const Iterator find_le(Key key, Int c, bool for_insert, Transaction &txn) {
        NodeBase *node = get_root(txn);
        if (node != NULL) {
            while(1) {
                find_le_fn fn(base::mgr(), &txn);
                NodeDispatcher::Dispatch(node, key, c, for_insert, base::mgr_, &txn, fn);
                if (fn.rtn) {
                    return fn.i_;
                }
                else {
                    node = fn.node_;
                }
            }
        }
        else {
            return Iterator(base::mgr_, &txn);
        }
    }

    const Iterator find_le(Key key, bool for_insert, Transaction &txn) {
        return find_le(key, 0, for_insert, txn);
    }
};

}
}
}

#endif	/* _CUBEFS_CORE_MAP_KV_FIND_HPP */

